package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //最小基因变化
        class Solution {
            // 四种碱基
            private static final char[] CH = {'A', 'C', 'G', 'T'};

            public int minMutation(String startGene, String endGene, String[] bank) {
                // 把 bank 放入哈希集合，O(1) 判断合法性
                Set<String> dict = new HashSet<>(Arrays.asList(bank));
                if (!dict.contains(endGene)) return -1; // 多数题面：目标必须可达

                // 访问集与队列
                Set<String> vis = new HashSet<>();
                Queue<String> q = new LinkedList<>();

                q.offer(startGene);
                vis.add(startGene);

                int steps = 0; // 变换次数 = 层数
                while (!q.isEmpty()) {
                    int size = q.size(); // 固定本层大小
                    for (int s = 0; s < size; s++) {
                        String cur = q.poll();
                        if (cur.equals(endGene)) return steps;

                        char[] arr = cur.toCharArray();
                        for (int i = 0; i < arr.length; i++) {
                            char old = arr[i];
                            for (char c : CH) {
                                if (c == old) continue; // 必须改变 1 位
                                arr[i] = c;
                                String next = new String(arr);
                                if (dict.contains(next) && vis.add(next)) {
                                    q.offer(next);       // 入队即标记
                                }
                            }
                            arr[i] = old; // 还原，为下一个位置生成邻居
                        }
                    }
                    steps++; // 本层处理完，次数 +1
                }
                return -1; // 无法到达
            }
        }


        //单词接龙
        class Solution2 {
            // 也可直接用 for (char c='a'; c<='z'; c++)
            static final char[] LETTERS = {
                    'a','b','c','d','e','f','g','h','i','j',
                    'k','l','m','n','o','p','q','r','s','t',
                    'u','v','w','x','y','z'
            };

            public int ladderLength(String beginWord, String endWord, List<String> wordList) {
                Set<String> dict = new HashSet<>(wordList);
                if (!dict.contains(endWord)) return 0; // 终点必须在字典中

                Queue<String> q = new LinkedList<>();
                Set<String> vis = new HashSet<>();

                q.offer(beginWord);
                vis.add(beginWord);

                int ret = 0; // 层号，表示已走的“边数”
                while (!q.isEmpty()) {
                    int size = q.size(); // 固定当前层大小
                    for (int i = 0; i < size; i++) {
                        String cur = q.poll();
                        if (cur.equals(endWord)) return ret + 1; // 单词数 = 已走边数 + 1

                        char[] ch = cur.toCharArray();
                        for (int j = 0; j < ch.length; j++) {
                            char old = ch[j];
                            for (char c : LETTERS) {
                                if (c == old) continue; // 避免自环
                                ch[j] = c;
                                String next = new String(ch);
                                if (dict.contains(next) && vis.add(next)) {
                                    q.offer(next);
                                }
                            }
                            ch[j] = old; // 回填
                        }
                    }
                    ret++; // 进入下一层
                }
                return 0; // 不可达
            }
        }

    }
}